package bstree

type Node struct {
	val         int
	left, right *Node
}

func NewNode(val int) *Node {
	return &Node{val, nil, nil}
}

type BSTree struct {
	Root *Node
}

func calculateDepth(n *Node, depth int) int {
	if n == nil {
		return depth
	}
	return Max(calculateDepth(n.left, depth+1), calculateDepth(n.right, depth+1))
}

func (t *BSTree) Depth() int {
	return calculateDepth(t.Root, 0)
}

func Exists(root *Node, val int) bool {
	if root == nil {
		return false
	}

	if root.val > val {
		return Exists(root.left, val)
	} else if root.val == val {
		return true
	} else {
		return Exists(root.right, val)
	}
}

func Insert(root *Node, val int) *Node {
	if root == nil {
		return NewNode(val)
	}

	if val < root.val {
		root.left = Insert(root.left, val)
	} else {
		root.right = Insert(root.right, val)
	}

	return root
}

func InOrderSuccessor(root *Node) *Node {
	cur := root
	for cur.left != nil {
		cur = cur.left
	}

	return cur
}

func BstDelete(root *Node, val int) *Node {
	if root == nil {
		return root
	}

	if val < root.val {
		root.left = BstDelete(root.left, val)
	} else if val > root.val {
		root.right = BstDelete(root.right, val)
	} else {
		if root.left == nil {
			return root.right
		} else if root.right == nil {
			return root.left
		} else {
			n := root.right
			d := InOrderSuccessor(n)
			d.left = root.left

			return root.right
		}
	}

	return root
}

func InOrder(root *Node) []int {
	traversal := make([]int, 0)
	inorderRecursive(root, &traversal)
	return traversal
}

func inorderRecursive(n *Node, traversal *[]int) {
	if n == nil {
		return
	}

	inorderRecursive(n.left, traversal)
	*traversal = append(*traversal, n.val)
	inorderRecursive(n.right, traversal)
}

func Max(a, b int) int {
	if a >= b {
		return a
	}
	return b
}
